#pragma once
#include<iostream>
#include<stdio.h>
#define valueType int
using namespace std;
namespace GIS20126
{
	struct node
	{
		valueType value;
		node* next = nullptr;
	};

	bool compare(valueType x, valueType y)
	{
		return x <= y;
	}
	node* function(node* root1, node* root2)
	{
		node* cur1 = root1;
		node* cur2 = root2;
		node* newroot=nullptr;
		node* tail = nullptr;
		while (cur1 != nullptr && cur2 != nullptr)
		{
			if (compare(cur1->value, cur2->value))
			{
				if (newroot == nullptr)
				{
					newroot = cur1;
					tail = newroot;
				}
				tail->next = cur1;
				cur1 = cur1->next;
			}
			else
			{
				if (newroot == nullptr)
				{
					newroot = cur2;
					tail = newroot;
				}
				tail->next = cur2;
				cur2 = cur2->next;
			}
			tail = tail->next;
		}
		if (cur1 != nullptr)
			tail = cur1;
		else
			tail = cur2;

		return newroot;
	}
}